package com.lx.algorithm.code.xly3.class03;

import static com.lx.algorithm.Utils.printMatrix;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-04 17:31:02
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-04     张李鑫                     1.0         1.0 Version
 */
public class Code03 {
    /**
     * 给定一个二维数组matrix，其中每个数都是正数，要求从左上到右下
     * 每一步只能向右或者向下，沿途经过的数字要累加起来
     * 最后请返回最小的路径和
     * <p>
     * 动态规划的空间压缩技巧！
     */

    public static int maxWays(int[][] matrix) {

        return process(matrix, 0, 0);
    }


    public static int process(int[][] matrix, int i, int j) {

        if (i == matrix.length - 1 && j == matrix[i].length - 1) {
            return matrix[i][j];
        }
        if (i == matrix.length - 1) {
            return matrix[i][j] + process(matrix, i, j + 1);
        }
        if (j == matrix[i].length - 1) {
            return matrix[i][j] + process(matrix, i + 1, j);
        }
        return Math.min(process(matrix, i + 1, j),
                process(matrix, i, j + 1)) + matrix[i][j];
    }


    /**
     * 二维动态动态规划
     *
     * @param matrix
     * @return
     */
    public static int dp(int[][] matrix) {
        int N = matrix.length - 1;
        int M = matrix[0].length - 1;
        int[][] dp = new int[N + 1][M + 1];
        dp[N][M] = matrix[N][M];


        for (int i = N - 1; i >= 0; i--) {
            dp[i][M] = dp[i + 1][M] + matrix[i][M];
        }

        for (int i = M - 1; i >= 0; i--) {
            dp[N][i] = dp[N][i + 1] + matrix[N][i];
        }

        for (int i = dp.length - 2; i >= 0; i--) {
            for (int j = dp[i].length - 2; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) + matrix[i][j];
            }
        }
        return dp[0][0];
    }


    // for test
    public static int[][] generateRandomMatrix(int rowSize, int colSize) {
        if (rowSize < 0 || colSize < 0) {
            return null;
        }
        int[][] result = new int[rowSize][colSize];
        for (int i = 0; i != result.length; i++) {
            for (int j = 0; j != result[0].length; j++) {
                result[i][j] = (int) (Math.random() * 10);
            }
        }
        return result;
    }

    /**
     * 空间优化 一维动态数组
     *
     * @param matrix
     * @return
     */
    public static int dpI(int[][] matrix) {
        int M = matrix[0].length - 1;
        int N = matrix.length - 1;
        int[] dp = new int[M + 1];
        dp[M] = matrix[matrix.length - 1][matrix[0].length - 1];
        for (int i = dp.length - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] + matrix[N][i];
        }

        for (int i = N - 1; i >= 0; i--) {
            dp[M] = dp[M] + matrix[i][M];
            for (int j = M - 1; j >= 0; j--) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + matrix[i][j];
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        int[][] m = generateRandomMatrix(10, 12);

        printMatrix(m);
        System.out.println(dp(m));
        System.out.println(dpI(m));
        System.out.println(maxWays(m));
    }
}
